package de.cau.apo.problems.travellingsalesman;

import java.util.LinkedList;
import java.util.List;

import de.cau.apo.container.BitIndexSet;
import de.cau.apo.exceptions.NotFeasibleException;
import de.cau.apo.problems.AbstractSolution;

/**
 * This class represents a possible solution of the traveling salesman problem.
 * It contains the tour that this solution represents and is responsive for 
 * checking the feasibility and calculating the objective value.
 * 
 * @author Marius Richter
 *
 */
public class TSPSolution extends AbstractSolution<TSPInstance> {

	// ########### properties ###########
	
	/** the tour that this solution represents */
	public final List<Node> tour = new LinkedList<Node>();
	
	// ########### instantiation ###########
	
	/**
	 * Creates a new empty solution for the traveling salesman problem.
     * @param instance the instance for that this solution shall be created
	 */
	public TSPSolution(TSPInstance instance) {
		super(instance);
	}
	
	// ########### getter/setter ###########
	
	/**
	 * add the given node at the end of the tour.
	 * @param nodeIndex the node to add
	 */
	public void addTourStop(int nodeIndex) {
		tour.add(getInstance().getNode(nodeIndex));
	}
	
	/**
	 * add the given node at the given index in the tour.
	 * @param nodeIndex the node to add
	 * @param tourIndex the index where the node shall be added
	 */
	public void addTourStop(int nodeIndex, int tourIndex) {
		tour.add(tourIndex, getInstance().getNode(nodeIndex));
	}
	
	/**
	 * remove the given node from the tour
	 * @param nodeIndex the node to remove
	 */
	public void removeNodeFromTour(int nodeIndex) {
		tour.remove(getInstance().getNode(nodeIndex));
	}
	
	/**
	 * remove the node from the tour that is positioned at the given index
	 * @param tourIndex the index of the node that shall be removed
	 */
	public void removeIndexFromTour(int tourIndex) {
		tour.remove(tourIndex);
	}
	
	/**
	 * remove the complete current tour.
	 */
	public void clear() {
		this.tour.clear();
	}
	
	// ########### AbstractSolution implementation ###########
	
	@Override
	public void decode(String solution) {
		this.clear();
		String[] tour = solution.split(" ");
		for (String tourStop : tour) {
			this.addTourStop(Integer.parseInt(tourStop));
		}
	}

	@Override
	public String encode() {
		String s = "";
		for (Node tourStop : this.tour) {
			s += tourStop.getIndex() + " ";
		}
		s.trim();
		return s;
	}

	@Override
	public double getObjValue() {
		Node from = getInstance().getNode(0);
		double costs = 0;
		for (Node tourStop : this.tour) {
			costs += from.getEdgeCost(tourStop);
			from = tourStop;
		}
		return costs;
	}

	@Override
	public void isFeasible() throws NotFeasibleException {
		BitIndexSet nodes = new BitIndexSet(getInstance().getNumNodes());
		for (Node tourStop : this.tour) {
			if (nodes.contains(tourStop.getIndex())) {
				throw new NotFeasibleException("Node '" + tourStop + "' has been visited twice.");
			}
			nodes.add(tourStop.getIndex());
		}
		if (nodes.size() != instance.getNumNodes()) {
			throw new NotFeasibleException("Not all nodes have been visited");
		}
	}

}
